/**
 * 剑指 Offer 43. 1～n 整数中 1 出现的次数
 * https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/
 */

/**
 * @param {number} n
 * @return {number}
 */
function countDigitOne(n) {
  // 分割出每一个数位
  const digits = [];
  let num = n;
  while (num) {
    digits.unshift(num % 10);
    num = Math.floor(num / 10);
  }
  // 计算每一个数位前的所有数位中 1 的个数，自个位向上消除数位时需要把前面的数位（父）的 1 的个数也计算进去
  const oneCountsPerDigit = new Array(digits.length);
  let preOneCount = 0;
  for (let i = 0; i < oneCountsPerDigit.length; i += 1) {
    oneCountsPerDigit[i] = preOneCount;
    if (digits[i] === 1) {
      preOneCount += 1;
    }
  }
  // 计算 9 到 999... 中的 1 的个数，消除数位时需要将其（子）中的 1 的个数也计算进去
  const oneCountsPerBase = new Array(digits.length);
  oneCountsPerBase[0] = 0;
  for (let i = 1; i < digits.length; i += 1) {
    oneCountsPerBase[i] = oneCountsPerBase[i - 1] * 10 + (10 ** (i - 1));
  }
  // 从后往前遍历位并消除，消除时需要计算出其中关联的父子数位中的 1 的个数以及其自身的 1 的个数
  let count = 0;
  for (let i = 0; i < digits.length; i += 1) {
    const digit = digits[digits.length - i - 1];
    // 计算当前位的子数值的所有 1 的个数
    count += (oneCountsPerBase[i] * digit);
    const base = 10 ** i;
    if (digit > 1) {
      // 如果当前位大于 1 时代表以 1 开头的所有子数位都包含 1
      count += base;
    } else if (digit > 0) {
      // 如果当前位是 1 时只需要再加 1，因为之前遍历时所有的子数位已经将其包含进去了
      count += 1;
    }
    // 消除当前位时将父位中的 1 的数量包含进去
    count += (oneCountsPerDigit[digits.length - i - 1] * (digit * base));
  }
  return count;
}

console.log(countDigitOne(1) === 1);
console.log(countDigitOne(9) === 1);
console.log(countDigitOne(99) === 20);
console.log(countDigitOne(99999) === 50000);
console.log(countDigitOne(10) === 2);
console.log(countDigitOne(1000) === 301);
console.log(countDigitOne(100000) === 50001);
console.log(countDigitOne(12) === 5);
console.log(countDigitOne(13) === 6);
console.log(countDigitOne(20) === 12);
